﻿#ifndef HEAP_H
#define HEAP_H
#include <fstream>
#include "../Def.h"
namespace CLRS
{
	template<class T>
	class Heap
	{
	public:
		~Heap()
		{
			delete[] m_pData;
			m_pData = NULL;
		}
		Heap()
		{
			m_pData = NULL;
			m_iLen = m_iHeapSize = 0;
		}

		Heap(T* pData,int len)
		{
			m_pData = new T[len];
			memcpy(m_pData,pData,len * sizeof(T));
			m_iLen = len;
			m_iHeapSize = len;
			BuildMaxHeap();
		}

		T GetHeapMaximum()
		{
			return m_pData[0];
		}

		bool ExtractHeapMax(T& element)
		{
			if (m_iHeapSize < 1)
			{
				std::cout << "heap underflow" << endl;
				return false;
			}
			element = m_pData[0];

			m_pData[0] = m_pData[m_iHeapSize - 1];
			m_iHeapSize--;
			MaxHeapify(0,m_iHeapSize);
			return true;
		}


		bool IncreaseHeapKey(int idx,T key)
		{
			if (key < m_pData[idx])
			{
				return false;
			}
			m_pData[idx] = key;
			while (idx>0 && m_pData[GetParent(idx)] < m_pData[idx])
			{
				SwapData(m_pData[idx],m_pData[GetParent(idx)]);
				idx = GetParent(idx);
			}
		}


		void InsertKey(T key)
		{
			m_iHeapSize ++;
			if (m_iHeapSize > m_iLen)
			{
				T * tempData = new T[2 * m_iHeapSize];
				if (m_iLen > 0)
				{
					CopyArray(m_pData,0,m_iLen,tempData,0);
				}
				m_iLen = 2 * m_iHeapSize;
				delete[] m_pData;
				m_pData = tempData;
			}
			/*m_pData[m_iHeapSize - 1] = SMALL_NUMBER;*/
			m_pData[m_iHeapSize - 1] = (T)SMALL_NUMBER;
			IncreaseHeapKey(m_iHeapSize - 1,key);
			
		}
		//建最大堆O(n) n为待排序数组长度
		void BuildMaxHeap()
		{
			int parentIdx = GetParent(m_iLen - 1);
			if (parentIdx >= 0)
			{
				for (int i = parentIdx;i>=0;i--)
				{
					MaxHeapify(i,m_iLen);
				}
			}

		}
		//将以id为根的子树变成最大堆(若子树高度为h,复杂度为
		//o(h))
		// 针对的数组为A[0:len - 1]
		void MaxHeapify(int idx,int len)
		{
			if (idx >= len)
			{
				return;
			}
			int leftIdx = GetLeft(idx);
			int rightIdx = GetRight(idx);
			//T largest = m_pData[idx];
			int largestIdx = idx;
			if (leftIdx < len && m_pData[leftIdx] > m_pData[largestIdx])
			{
				largestIdx = leftIdx;
			}
			if (rightIdx < len && m_pData[rightIdx] > m_pData[largestIdx])
			{
				largestIdx = rightIdx;
			}

			if (largestIdx != idx)
			{
				SwapData(m_pData[idx],m_pData[largestIdx]);
				MaxHeapify(largestIdx,len);
			}
		}
		int GetRootIndice()
		{
			return 0;
		}
		int GetParent(int i)
		{
			return floor((i - 1) / 2.0);
		}
		int GetLeft(int i)
		{
			return 2 * i + 1;
		}
		int GetRight(int i)
		{
			return 2 * i + 2;
		}

		bool IsRoot(int i)
		{
			return i == 0;
		}
	private:
		T* m_pData;
		int m_iLen;
		int m_iHeapSize;
	};
}
#endif